package main

import (
	"fmt"
)

/*
在排序数组中查找数字
统计一个数字在排序数组中出现的次数。

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
*/

//暴力解法
/*
func erfen(nums []int, target int) int {
	leftmost := sort.SearchInts(nums, target)
	if leftmost == len(nums) || nums[leftmost] != target
		return 0
	}
	rightmost := sort.SearchInts(nums, target + 1) - 1
	return rightmost - leftmost + 1
}
*/

//二分法
func search(nums []int, target int) int {
	// 二分查找，返回target的数量，题34改进版，只需起始位置，然后遍历过去
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)>>1
		if target > nums[mid] {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	leftIdx := left
	// fast way
	if leftIdx == len(nums) || nums[leftIdx] != target {
		return 0
	}
	// 存在于数组中
	res := 0
	for i := leftIdx; i < len(nums); i++ {
		if nums[i] == nums[leftIdx] {
			res++
		} else {
			break
		}
	}
	return res
}

func main() {
	nums := []int{5, 7, 7, 8, 8, 10}
	fmt.Println(search(nums, 8))
}
